﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace TrabajoPractico1
{
    public partial class ExpansionCombinatoria : Form
    {
        public ExpansionCombinatoria()
        {
            InitializeComponent();
        }

        #region Eventos

        private void ExpansionCombinatoria_Load(object sender, EventArgs e)
        {
            // coloco la imagen inicial
            pibEnunciado.Image = TrabajoPractico1.Properties.Resources.Zoologico;
        }

        private void salirToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.Close();
        }

        // evento que se dispara al presionar el boton de Expansion combinatoria, resuelve el problema
        private void btnExpansión_Click(object sender, EventArgs e)
        {
            this.ResolverProblema(1);
        }

        // evento que se dispara al presionar el boton de Ramificacion y poda, resuelve el problema
        private void btnRamificacion_Click(object sender, EventArgs e)
        {
            this.ResolverProblema(2);
        }

        private void enunciadoToolStripMenuItem_Click(object sender, EventArgs e)
        {
            string enunciado = "Un sábado soleado de primavera, un niño y sus padres deciden " +
                "salir de paseo al zoológico de la ciudad. Para esto, comienzan el recorrido desde " +
                "la entrada del zoo, representada en la imagen que se muestra a continuación como Zoológico. " +
                "La familia tiene como objetivo visitar a todos los animales presentes, en una forma tal " +
                "de que lleguen a la salida, caminando lo menos posible. ";

            MessageBox.Show(enunciado,"Enunciado",MessageBoxButtons.OK, MessageBoxIcon.Information);
        }

        private void cargarDatosToolStripMenuItem_Click(object sender, EventArgs e)
        {
            // implementar carga de datos por parte del usuario
        }

        private void expansiónCombinatoriaToolStripMenuItem_Click(object sender, EventArgs e)
        {
            string info = "EXPANSIÓN COMBINATORIA \n\n"+
                "En informática, la búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o "+
                "simplemente fuerza bruta, es una técnica trivial pero a menudo usada, que consiste en enumerar "+
                "sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de "+
                "chequear si dicho candidato satisface la solución al mismo. \n"+
                "La búsqueda por fuerza bruta es sencilla de implementar y, siempre que exista, encuentra una solución. "+
                "Sin embargo, su coste de ejecución es proporcional al número de soluciones candidatas, el cual es "+
                "exponencialmente proporcional al tamaño del problema. Por el contrario, la búsqueda por fuerza bruta "+
                "se usa habitualmente cuando el número de soluciones candidatas no es elevado, o bien cuando éste puede "+
                "reducirse previamente usando algún otro método heurístico. Es un método utilizado también cuando es más "+
                "importante una implementación sencilla que una mayor rapidez. \n\n"+
                "Fuente: Wikipedia, Búsqueda de fuerza bruta. ";

            MessageBox.Show(info, "Ayuda", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }

        private void ramificaciónYPodaToolStripMenuItem_Click(object sender, EventArgs e)
        {
            string info = "RAMIFICACIÓN Y PODA: \n\n"+
                "El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y "+
                "Acotación) es una variante del Backtracking mejorado sustancialmente. El término (del "+
                "inglés, Branch and Bound) se aplica mayoritariamente para resolver cuestiones o problemas "+
                "de optimización. "+
                "La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde "+
                "cada rama nos lleva a una posible solución posterior a la actual. La característica de esta "+
                "técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se "+
                "encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para "+
                "«podar» esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan "+
                "de la solución óptima. \n\n"+
                "Fuente: Wikipedia, Ramificación y poda.";

            MessageBox.Show(info, "Ayuda", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }

        #endregion

        #region Métodos

        public void ResolverProblema(int algoritmo)  // algoritmo puede recibir los valores: 1- Expansion combinatoria; 2- Ramificacion y poda
        {
            int[,] matrizDistancias = this.CargarDatos();
            switch (algoritmo)
            {
                case 1:
                    this.ResolverExpansion(matrizDistancias); 
                    break;
                case 2:
                    this.ResolverRamificacion(matrizDistancias);
                    break;
            }
        }

        // cargo la matriz de disctancias con los datos por defecto
        public int[,] CargarDatos()
        {
            int[,] matrizDistancias = new int[6,6]{ { 0,1543, 1510, 1203, 1043, 1},
                                                    {1543 , 0, 99 , 340, 500 ,  1},
                                                    {1510, 99 , 0 , 307, 467 ,  1},
                                                    {1203, 340, 307, 0 , 160 ,  1},
                                                    {1043, 500, 467, 160, 0  ,  1},
                                                    {1,     1,  1,   1,   1,    0}};
            
            return matrizDistancias;
        }

        // metodo que resuelve el problema aplicando el algoritmo de expansión combinatoria
        public void ResolverExpansion(int[,] matrizDist)
        {
            // guardo y muestro la hora de inicio de ejecución
            DateTime inicio = DateTime.Now;
            txtEstadisticasExp.Text = " Inicio ejecución: ";
            this.MostrarDateTime(this.txtEstadisticasExp, inicio);

            int ind=0, min=10000, indiceMin=0;
            int[] perm = new int[5];
            bool ban;
            
            Recorrido[] arrayPer = new Recorrido[120];

            // genero las permutaciones de todos los posibles recorridos y calculo las distancias
            for(int i=12345;i<=54321;i++)
            {
                    //convierto los numeros enteros en un arreglo de enteros               
                    perm[0]= (i%100000)/10000;
                    perm[1]= (i%10000)/1000;
                    perm[2]= (i%1000)/100;
                    perm[3]= (i%100)/10;
                    perm[4]= i%10;
                    ban=false;
             
                    for(int h=0; h<5; h++)  
                    {
                        //valido que el numero no contenga 0,6,7,8 o 9              
                        if ((perm[h] != 0) && (perm[h] != 6) && (perm[h] != 7) && (perm[h] != 8) && (perm[h] != 9))
                        {
                            ban = true;
                        }
                        else
                        {
                            ban = false;
                            break;
                        }
                    } 
                    if(ban)
                    {
                        //valido que todos los numeros dentro del numero sean distintos
                        if((perm[0]!= perm[1])&&(perm[0]!=perm[2])&&(perm[0]!= perm[3])&&(perm[0]!=perm[4])&&
                            (perm[1]!= perm[2])&&(perm[1]!=perm[3])&&(perm[1]!= perm[4])&&
                            (perm[2]!= perm[3])&&(perm[2]!=perm[4])&&(perm[3]!= perm[4]) )
                        { 
                            ban=true;
                        } 
                        else
                        {
                            ban=false;
                        } 
                    }
                
                    //valido si se cumplieron las condiciones anteriories y si la suma del arreglo es 15(1+2+3+4+5)       
                    if((ban)&&(perm[0]+perm[1]+perm[2]+perm[3]+perm[4])==15)  
                    {
                        arrayPer[ind] = new Recorrido();
                        arrayPer[ind].totalDistancia = 0;                                                     
                        //guardo los nodos recorridos                                                                                              
                        for(int k=0;k<5;k++)
                        {
                            arrayPer[ind].nodosRecorridos[k] = perm[k]-1;
                        } 

                        //calculo la cantidad de Km recorridos
                        arrayPer[ind].totalDistancia += matrizDist[perm[0] - 1, 5];
                        for(int k=0;k<4;k++)
                        {
                            arrayPer[ind].totalDistancia += matrizDist[perm[k]-1, (perm[k+1]-1)];
                        }   
                        arrayPer[ind].totalDistancia += matrizDist[(perm[4]-1), 5];      
                        ind++;   
                    }                
            }

            // busco el menor recorrido
            for (int i = 0; i < 120; i++)
            {
                if (arrayPer[i].totalDistancia < min)
                {
                    indiceMin = i;
                    min = arrayPer[i].totalDistancia;
                }
            }

            // cambia a la imagen con la solucion graficada
            pibEnunciado.Image = TrabajoPractico1.Properties.Resources.ZoologicoSolucion;

            // muestro la cantidad de recorridos generados
            txtEstadisticasExp.Text += " Cantidad de recorridos generados: " + ind + "\r\n" + "\r\n";
            
            // muestro las estadisticas de la resolucion
            this.MostrarEstadisticas(this.txtEstadisticasExp, arrayPer, indiceMin);

            // guardo y muestro fin de ejecuacion
            DateTime fin = DateTime.Now;
            txtEstadisticasExp.Text += " Fin ejecución: ";
            this.MostrarDateTime(this.txtEstadisticasExp, fin);
            // muestro tiempo total de procesamiento
            txtEstadisticasExp.Text += " Tiempo procesamiento: " + (fin-inicio).Seconds + ":" + (fin-inicio).Milliseconds;
        }

        // metodo que resuelve el problema aplicando el algoritmo de ramificacion y poda
        public void ResolverRamificacion(int[,] matrizDist)
        {
            // guardo y muestro la hora de inicio de ejecución
            DateTime inicio = DateTime.Now;
            txtEstadisticasRam.Text = " Inicio ejecución: ";
            this.MostrarDateTime(this.txtEstadisticasRam, inicio);

            int[] perm = new int[5];
            int ind = 0;
            int min=10000;
            // defino el arreglo que contendra todos los recorridos, como maximo seran 5!=120
            Recorrido[] arrayPer = new Recorrido[120];

            // for anidados para generar las permutaciones
            for (int h = 1; h <= 5; h++)
            {
                for (int i = 1; i <= 5; i++)
                {
                    for (int j = 1; j <= 5; j++)
                    {
                        for (int k = 1; k <= 5; k++)
                        {
                            for (int l = 1; l <= 5; l++)
                            {
                                // valido que no se asigne 2 veces el mismo numero -> me aseguro que sean permutaciones
                                if (h != i && h != j && h != k && h != l && i != j && i != k && i != l && j != k && j != l && k != l)
                                {    
                                    // inicializo los recorridos y pongo en 0 el total de distancia
                                    arrayPer[ind] = new Recorrido();
                                    arrayPer[ind].totalDistancia = 0;

                                    perm[0] = h;
                                    perm[1] = i;
                                    perm[2] = j;
                                    perm[3] = k;
                                    perm[4] = l;

                                    //calculo la cantidad de metros recorridos
                                    arrayPer[ind].totalDistancia += matrizDist[perm[0] - 1, 5];
                                    for (int y = 0; y < 4; y++)
                                    {
                                        arrayPer[ind].totalDistancia += matrizDist[perm[y] - 1, (perm[y + 1] - 1)];
                                    }
                                    arrayPer[ind].totalDistancia += matrizDist[(perm[4] - 1), 5];

                                    if (arrayPer[ind].totalDistancia < min)
                                    {
                                        //guardo los nodos recorridos                                                                                              
                                        for (int y = 0; y < 5; y++)
                                        {
                                            arrayPer[ind].nodosRecorridos[y] = perm[y] - 1;
                                        }

                                        // actualizo el minimo recorrido
                                        min = arrayPer[ind].totalDistancia;

                                        // aumento el indice del arreglo
                                        ind++;
                                    }  
                                }
                            }
                        }
                    }
                }
            }

            // cambia a la imagen con la solucion graficada
            pibEnunciado.Image = TrabajoPractico1.Properties.Resources.ZoologicoSolucion;

            // muestro la cantidad de recorridos generados
            txtEstadisticasRam.Text += " Cantidad de recorridos generados: " + ind + "\r\n" + "\r\n";

            // muestro las estadisticas de la resolucion
            this.MostrarEstadisticas(this.txtEstadisticasRam, arrayPer, ind-1);

            // guardo y muestro fin de ejecuacion
            DateTime fin = DateTime.Now;
            txtEstadisticasRam.Text += " Fin ejecución: ";
            this.MostrarDateTime(this.txtEstadisticasRam, fin);
            // muestro tiempo total de procesamiento
            txtEstadisticasRam.Text += " Tiempo procesamiento: " + (fin - inicio).Seconds + ":" + (fin - inicio).Milliseconds;

        }

        // metodo en el que se muestra el menor recorrido, los nodos recorridos y la distancia minima
        public void MostrarEstadisticas(TextBox textBox, Recorrido[] arrayPer, int indiceMin)
        {
            string[] nombreNodos = new string[6] { "Cebra", "Hipopótamo", "León", "Pingüinos", "Jirafa", "Entrada/Fin Zoo" };

            textBox.Text += " Menor recorrido: \r\n";
            textBox.Text += "- " + nombreNodos[5] + "\r\n";
            for (int i = 0; i < 5; i++)
            {
                textBox.Text += "- " + nombreNodos[(arrayPer[indiceMin].nodosRecorridos[i])] + "\r\n";
            }
            textBox.Text += "- " + nombreNodos[5] + "\r\n" + "\r\n";
            textBox.Text += " Total de metros recorridos: " + arrayPer[indiceMin].totalDistancia + "\r\n" + "\r\n";
        }

        // metodo que muestra la hora en un textbox
        public void MostrarDateTime(TextBox textBox, DateTime hora)
        {
            textBox.Text += hora.Hour + ":" + hora.Minute + ":" + hora.Second + ":" + hora.Millisecond + "\r\n" + "\r\n";
        }

        #endregion

    }


    // defino una clase que contendra un recorrido completo
    public class Recorrido
    {
        public int[] nodosRecorridos = new int[5];
        public int totalDistancia;
    }

}
